#!/usr/bin/python
# Filename: String.py

# KMP algorithm of string

def proper_vector(s):
    '''return a s' proper vector as a list'''
    p = [0] * len(s)
    for i in range(1, len(s)):
        k = p[i-1]
        while (s[i] != s[k]) and (k != 0):
        # this loop will keep s[i-1] has an as long as possible prefix, that is:
        # k = p[k-1]: decrease the prefix once
        # check(s[i] == s[k]): whether s[i] matches this prefix
        # for example: abababc, (s[i] == c) != (s[k] == s[p[i-1]] = s[4] = a)
        # k = p[k-1] = p[3] = 2, of cource s[0:2] is also a prefix for s[i-1]
        # then check whether s[i] matches this prefix
            k = p[k-1]
        if s[i] == s[k]:
        # if k = p[i-1]:
        # s[i] = s[s[i-1]], the prefix increased
        # else:
        #
            p[i] = k+1
        else:
            p[i] == 0
    return p

def kmp_match(s, l):
    '''return the first index if s is a sub-string of l, or else return -1'''
    p = proper_vector(s)
    if len(s) > len(l):
        return -1
    i = 0 # pointer of s
    for j in range(len(l)+1):
    # +1 is  bcz j will equal to len(l) if match happens in the end of l
        if i == len(s): return j-i
        while l[j] != s[i] and i != 0:
            i = p[i-1]
        if l[j] == s[i]:
            i += 1
            j += 1
    return -1
    # discuss on efficiency:
    # i increased j(len(l)) times at most, 
    # so i = p[i-1] runs at most j(len(l)) times in the whole loop.
    # that is to say the efficiency of loop is O(len(l) + len(l)) = O(len(l)).
    # and efficientcy of proper_vector is similar, O(len(s))

def max_common_substring(s1, s2):
    '''return max common sub-string of s1 and s2, if none, return ""'''
    # ex_DSIntro_3_3
    # caution: mcs can be several, here only return the first
    mcs = ""
    i = 0
    while i < len(s1)-len(mcs):
    # compared with for i in range(len(s1)),
    # which one is more efficient is a question
        j = 0
        while j < len(s2)-len(mcs):
            if s1[i] == s2[j]:
                # find a max common sub-string
                k = 1
                while i+k<len(s1) and j+k<len(s2) and s1[i+k] == s2[j+k]: k += 1
                if k > len(mcs): 
                    mcs = s1[i:i+k]
                # here's maybe a mistake of the book's answer
                # j += k is wrong, it will lead missing mcs of strings such as
                # "abcabd" and "abcabcabd"
                j += 1
            else:
                j += 1
        i += 1
    return mcs

def delete(s, start, length):
    # ex_DSIntro_work_3_3
    l = [i for i in s]
    if start < 0 or start >= len(s): return s
    if start+length > len(s):
        length = len(s)-start
    l.append(None)
    for i in range(start, len(s)-length+1):
        l[i] = l[i+length]
    r = ""
    for i in l:
        if i: r += i
        else: break
    return r

if __name__ == "__main__":
    def ex_DSIntro_3_2():
        # ex_DSIntro_3_2
        s = 'A B C D E F G H'
        print "proper vector of %s is %s" % (s, proper_vector(s))
        s = 'I I I I I I I I'
        print "proper vector of %s is %s" % (s, proper_vector(s))
        s = 'B A B B A B A B'
        print "proper vector of %s is %s" % (s, proper_vector(s))

    ex_DSIntro_3_2()

    s = "aaaabaaaac"
    print "proper vector of %s is %s" % (s, proper_vector(s))
    s = "abababcababababc"
    print "proper vector of %s is %s" % (s, proper_vector(s))
    s0 = "abc"
    print "kmp_match(%s, %s): %d" % (s0, s, kmp_match(s0, s))
    s = " a b a b b a a b a a "
    s0 = " a a b "
    print "kmp_match(%s, %s): %d" % (s0, s, kmp_match(s0, s))

    s1 = "abcdefghijklmn"
    s2 = "abdefklmn"
    print "max_common_substring(%s, %s): %s" % (s1, s2, max_common_substring(s1, s2))
    s1 = "abcabd"
    s2 = "abcabcabd"
    print "max_common_substring(%s, %s): %s" % (s1, s2, max_common_substring(s1, s2))

    s = "abcdefghijk"
    print "delete(%s, %d, %d): %s" % (s, 2, 3, delete(s, 2, 3))
    print "delete(%s, %d, %d): %s" % (s, 2, 10, delete(s, 2, 10))
